Computer applications request read and write access to information storage systems (e.g., computer disk drive systems) in order to perform their respective functions. A variety of different scheduling algorithms have been developed to improve the performance of such information storage systems.
Among the algorithms that are used for scheduling non-realtime access requests are the SCAN algorithm and the Circular SCAN (or C-SCAN) algorithm. The SCAN algorithm involves moving the mechanical arm of a disk based information storage system in alternate directions and servicing all requests that lie in the scan path in each direction. In accordance with the Circular SCAN algorithm, the mechanical arm scans in one direction and, after serving the last request in the SCAN direction, the arm returns to a start position without servicing any requests as it returns.
Among the algorithms that are used for scheduling realtime access requests are the Earliest-Deadline-First (EDF) algorithm, the Feasible-Deadline-SCAN (FD-SCAN) algorithm, and the Deadline Sensitive SCAN (DS-SCAN) algorithm. The EDF algorithm involves selecting the request with the earliest deadline for service. The FD-SCAN algorithm involves using the track location of the request with earliest feasible deadline (i.e., a deadline that can be met) to determine the SCAN direction at each scheduling point. The DS-SCAN algorithm is a hybrid of the traditional EDF and SCAN algorithms that approximates the behavior of the SCAN algorithm, subject to the requirement that completion deadlines of the realtime access requests are met.
What is needed are improved systems and methods of scheduling information storage system access requests.